package graph.unweighted.dfs;

import java.util.ArrayList;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: CandyDFS.java 
 * @Package graph.dfs 
 * @Description: 图的深度优先遍历
 * @author CandyWall   
 * @date 2021年1月14日 下午7:48:11 
 * @version V1.0
 */
public class CandyDFS {
    private CandyGraph graph;
    private boolean[] visited;  //记录顶点是否被遍历过，默认都为false
    public CandyDFS(CandyGraph graph) {
        this.graph = graph;
        visited = new boolean[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
        }
        dfs();
    }
    
    private ArrayList<Integer> preOrderList = new ArrayList<>();    // 深度优先遍历的前序结果
    private ArrayList<Integer> postOrderList = new ArrayList<>();   // 深度优先遍历的后序结果
    
    public void dfs() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                dfs(v);
            }
        }
    }
    /**
     * 深度优先遍历
     */
    private void dfs(int v) {
        visited[v] = true;
        preOrderList.add(v);
        for(int w : graph.adjacentVertexes(v)) {
            if(!visited[w]) {
                dfs(w);
            }
        }
        postOrderList.add(v);
    }
    
    public ArrayList<Integer> getPreOrderList() {
        return preOrderList;
    }

    public ArrayList<Integer> getPostOrderList() {
        return postOrderList;
    }
    
    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/graph.txt");
        CandyDFS dfs = new CandyDFS(graph);
        System.out.println("深度优先遍历的前序结果：" + dfs.getPreOrderList());
        System.out.println("深度优先遍历的有序结果：" + dfs.getPostOrderList());
    }
}
